package leetcode.templates.sorts;

import leetcode.helper.HelpDebug;

public class MaxQuickSort {

	public void sort(int[] nums) {
		randomSort(nums, 0, nums.length - 1);
	}

	private void randomSort(int[] nums, int L, int R) {
		if (L >= R) {
			return;
		}
		int index = this.random(L, R);
		index = this.sort(nums, L, R, index);
		this.randomSort(nums, L, index - 1);
		this.randomSort(nums, index + 1, R);
	}

	private int sort(int[] nums, int L, int R, int index) {
		this.swap(nums, index, R);
		int num = nums[R];
		int p = L;
		for (int i = L; i < R; i++) {
			if (nums[i] < num) {
				this.swap(nums, p++, i);
			}
		}
		this.swap(nums, p, R);
		return p;
	}

	private void swap(int[] nums, int index, int r) {
		int tmp = nums[index];
		nums[index] = nums[r];
		nums[r] = tmp;
	}

	private int random(int l, int r) {
		return (int) (Math.random() * (r - l + 1)) + l;
	}

	public static void main(String[] args) {
		MaxQuickSort mss = new MaxQuickSort();
		int[] array = HelpDebug.str2array3("[5,4,19,2,7,7,7,1,10,4,3]");
		mss.sort(array);
		HelpDebug.print(array);
		// [0,1) [l,r)
//		int l = 4, r = 9;
//		for (int i = 0; i < 10; i++) {
//			int ans = (int) (Math.random() * (r - l + 1)) + l;
//			System.out.println(ans);
//		}
	}

}
